# 将有序数组转换为二叉搜索树： https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        """
            感觉可以写一个插入函数，一个个插入
            这里写一个递归， 通过中序数组(二叉搜索树)， 创建二叉树即可
        """
        def createTree(nums, left, right):
            if left > right: return None

            root_index = (left + right) // 2
            node = TreeNode(nums[root_index])
            node.left = createTree(nums, left, root_index - 1)
            node.right = createTree(nums, root_index + 1, right)

            return node

        return createTree(nums, 0, len(nums) - 1)